/*
 * @lc app=leetcode.cn id=72 lang=java
 *
 * [72] 编辑距离
 */

import java.util.Arrays;

// @lc code=start
class Solution {

    int[][] memo;   // 记忆化搜索---备忘录
    public int minDistance(String word1, String word2) {
        // 动态规划
        // // dp[i][j]表示word1的前i个字符转换为word2的前j个字符所需要的最少操作数
        
        // int m = word1.length(), n = word2.length();

        // int[][] dp = new int[m+1][n+1];

        // // 初始化---边界条件---当一个字符串为空时，转换为另一个字符串所需要的最少操作数
        // for (int i = 0; i <= m; i++) {
        //     dp[i][0] = i;
        // }
        // for (int j = 0; j <= n; j++) {
        //     dp[0][j] = j;
        // }

        // for(int i = 1; i <= m; i++) {
        //     for(int j = 1; j <= n; j++) {
        //         if (word1.charAt(i-1) == word2.charAt(j-1)) {
        //             dp[i][j] = dp[i-1][j-1]; // 不需要操作
        //         } else {
        //             // 三种操作方式：插入、删除、替换
        //             dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i][j-1], dp[i-1][j])) + 1;
        //         }
        //     }
        // }
        // return dp[m][n];

        //动态规划--自底向上--- 优化空间复杂度
        int m = word1.length(), n = word2.length();
        memo = new int[m][n];
        for(int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dp(word1, m-1, word2, n-1);
    }

    private int dp(String s1, int i, String s2, int j) {
        if(i == -1) return j + 1;
        if(j == -1) return i + 1;

        if(memo[i][j] != -1) return memo[i][j];

        // 两个字符相等，不需要操作
        if(s1.charAt(i) == s2.charAt(j)) {
            memo[i][j] = dp(s1, i-1, s2, j-1);
        } else {
            // 三种操作方式：插入、删除、替换
            memo[i][j] = Math.min(dp(s1, i-1, s2, j-1), Math.min(dp(s1, i, s2, j-1), dp(s1, i-1, s2, j))) + 1;
        }
        return memo[i][j];
    }
}
// @lc code=end

